#  Copyright 2012 Sean Sherrard
#
#  Licensed under the Apache License, Version 2.0 (the "License");
#  you may not use this file except in compliance with the License.
#  You may obtain a copy of the License at
#
#      http://www.apache.org/licenses/LICENSE-2.0
#
#  Unless required by applicable law or agreed to in writing, software
#  distributed under the License is distributed on an "AS IS" BASIS,
#  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
#  See the License for the specific language governing permissions and
#  limitations under the License.

"""asn1 - Python library for encoding/decoding ASN.1 data

blah blah
"""

__author__ = 'Sean Sherrard'
__version__ = '1.2'
__copyright__ = "Copyright 2012, Sean Sherrard"

__all__ = ['dump', 'dumps', 'load', 'loads', 'Encoder', 'Decoder']

import sys
import math
import codecs
import re
from io import BytesIO
from datetime import date, time, datetime, timedelta, tzinfo
#from time import tzname, daylight, timezone, altzone
import time as tmod

PY3K = sys.version_info >= (3,0)
if PY3K:
	from struct import pack
	IntType = int
	StrType = str
else:
	from binascii import hexlify, unhexlify
	IntType = (int, long)
	StrType = unicode

USE_DECIMAL = True
if USE_DECIMAL:
	from decimal import Decimal

USE_LOGGING = True
if USE_LOGGING:
	import logging
	log = logging.getLogger(__name__)

if True:
	from pprint import PrettyPrinter
	class MyPrinter(PrettyPrinter):
		def format(self, object, context, maxlevels, level):
			r = repr(object)
			if len(r) > self._width:
				return r[:self._width-4]+'...'+r[-1], False, False
			else:
				return PrettyPrinter.format(self, object, context, maxlevels, level)
	pr = MyPrinter(width=60).pprint

# ===========================================================================

# ASN.1 Tag Classes and Universal Tag Numbers

UNIVERSAL = 0
APPLICATION = 1
CONTEXT = 2
PRIVATE = 3

EOC =               0 # End-Of-Contruction sentinel
BOOLEAN =           1 # bool
INTEGER =           2 # int or long
BIT_STRING =        3 # BitString
OCTET_STRING =      4 # bytes
NULL =              5 # None
OBJECT_IDENTIFIER = 6 # ObjectID
OBJECT_DESCRIPTOR = 7 # string
EXTERNAL =          8 # EmbeddedValue
REAL =              9 # float
ENUMERATED =       10 # Enumerated
EMBEDDED_PDV =     11 # EmbeddedValue
UTF8_STRING =      12 # string
RELATIVE_OID =     13 # ObjectID
TIME =             14 # string
SEQUENCE =         16 # Sequence, list or tuple
SET =              17 # Set, set or frozenset
#NUMERIC_STRING =   18 # string
#PRINTABLE_STRING = 19 # string
#TELETEX_STRING =   20 # string
#T61_STRING = TELETEX_STRING
#VIDEOTEX_STRING =  21 # string
#IA5_STRING =       22 # string
UTC_TIME =         23 # datetime with tzinfo == UTC
GENERALIZED_TIME = 24 # datetime with tzinfo != UTC
#GRAPHIC_STRING =   25 # string
#VISIBLE_STRING =   26 # string
#ISO646_STRING = VISIBLE_STRING
#GENERAL_STRING =   27 # string
#UNIVERSAL_STRING = 28 # string
CHARACTER_STRING = 29 # EmbeddedValue
#BMP_STRING =       30 # string
DATE =             31 # date
TIME_OF_DAY =      32 # time
DATE_TIME =        33 # datetime without tzinfo
DURATION =         34 # string
OID_IRI =          35 # string
RELATIVE_OID_IRI = 36 # string

# ===========================================================================

# ASN.1 Public Interface

def dump(obj, file, encoding='BER', strtype=None, segsize=None):
	Encoder(file=file, encoding=encoding, strtype=strtype, segsize=segsize).dump(obj)

def dumps(obj, encoding='BER', strtype=None, segsize=None):
	return Encoder(encoding=encoding, strtype=strtype, segsize=segsize).dumps(obj)

def load(file, encoding='BER', strict=True):
	# verify that we're at the EOF? pickle doesn't but json does
	return Decoder(file=file, encoding=encoding, strict=strict).load()

def loads(data, encoding='BER', strict=True):
	return Decoder(encoding=encoding, strict=strict).loads(data)

class Encoder(object):

	def __init__(self, file=None, encoding='BER', strtype=None, segsize=None):
		if encoding not in ('BER', 'DER', 'CER'):
			raise ValueError('invalid ASN.1 encoding: {}'.format(encoding))
		if strtype is not None and not isinstance(strtype, CharacterString):
			raise ValueError('invalid ASN.1 string type: {}'.format(strtype))
		if segsize is not None and (encoding != 'BER' or not (1 <= segsize <= 2147483647)):
			raise ValueError('invalid ASN.1 segment size for {} encoding'.format(encoding))
		if encoding == 'CER':
			segsize = 1000
		self._file = file
		self._encoding = encoding
		self._strtype = strtype
		self._segsize = segsize

	def dump(self, obj):
		if self._file is None:
			raise ValueError('dump() can only be used with file-based Encoder')
		length, elem = _encode_item(self, obj)
		_dump_element(self._file.write, elem)

	def dumps(self, obj):
		if self._file is not None:
			raise ValueError('dumps() can only be used with string-based Encoder')
		file = BytesIO()
		length, elem = _encode_item(self, obj)
		_dump_element(file.write, elem)
		assert file.tell() == length
		return file.getvalue()

class Decoder(object):

	def __init__(self, file=None, encoding='BER', strict=True):
		if encoding not in ('BER', 'DER', 'CER'):
			raise ValueError('invalid ASN.1 encoding: {}'.format(encoding))
		self._file = file
		self._offset = 0
		self._encoding = encoding
		self._strict = strict

	def load(self):
		if self._file is None:
			raise ValueError('load() can only be used with file-based Decoder')
		try:
			item = _decode_item(self, self._file)
		except EOFError:
			item = None
		return item

	def loads(self, data):
		if self._file is not None:
			raise ValueError('loads() can only be used with string-based Decoder')
		file = BytesIO(data)
		self._offset = 0
		try:
			item = _decode_item(self, file)
		except EOFError:
			item = None
		if self._offset != len(data):
			_decoding_error(self, 'extra data')
		return item

class ASN1Error(Exception):
	pass

class EncodingError(ASN1Error):
	pass

class DecodingError(ASN1Error):
	pass

# ===========================================================================

# ASN.1 Object Subtype Definitions

class CharacterString(unicode):
	__slots__ = []

class IRIString(unicode):
	__slots__ = []

class BitString(bytes):
#	__slots__ = ['_pad']  # can't have non-empty slots on str subclasses
	def __new__(cls, *args):
		if len(args) == 0:
			self = bytes.__new__(cls)
			self._pad = 0
		elif len(args) == 1:
			if isinstance(args[0], IntType):
				self = bytes.__new__(cls, uitob(args[0]))
			else:
				self = bytes.__new__(cls, args[0])
			self._pad = 0
		elif len(args) == 2:
			if isinstance(args[0], str):
				arg = int(args[0], args[1])
				m, e = math.frexp(args[1])
				bpd = e - (1 if m == 0.5 else 0)
				bitlen = len(args[0]) * bpd # num digits * bits per digit
				shift = ((bitlen + 7) & ~7) - bitlen
				self = bytes.__new__(cls, uitob(arg << shift))
				self._pad = shift & 7
			else:
				self = bytes.__new__(cls, args[1])
				self._pad = args[0]
				if pad > 7 or (pad and not self):
					raise ValueError('invalid pad value')
		else:
			raise TypeError('BitString constructor takes 1 or 2 args')
		return self
	def __int__(self):
		return btoui(self)
	def __index__(self):
		return btoui(self)
	def __hex__(self):
		return '0x' + hexlify(self)
	def bit_length(self):
		return len(self)*8 - self._pad

class Enumerated(int):
	__slots__ = []

class ObjectID(object):
	__slots__ = ['_value']
##	def __new__(cls, *args):
##		if not args:
##			raise TypeError('ObjectID can not be null')
##		value = ()
##		for part in args[:-1]:
##			if isinstance(part, ObjectID):
##				part = part._value if part._value[0] is not None else part._value[1:]
##			value += tuple(part)
##		part = args[-1]
##		if isinstance(part, str):
##			part = [int(x) if x else None for x in part.split('.')]
##		value += tuple(part)
##		if len(value) < 2:
##			raise ValueError('ObjectID must have at least 2 components')
##		self = object.__new__(cls)
##		self._value = value
##		return self
	def __new__(cls, arg):
		if isinstance(arg, ObjectID):
			arg = arg._value
		elif isinstance(arg, str):
			arg = tuple([int(x) if x else None for x in arg.split('.')])
		elif not isinstance(arg, tuple):
			raise TypeError('ObjectID initializer must be string, tuple, or ObjectID')
		if len(arg) < 2:
			raise ValueError('ObjectID must have at least 2 components')
		self = object.__new__(cls)
		self._value = arg
		return self
	def __add__(self, other):
		if isinstance(other, ObjectID):
			if other._value[0] is not None:
				raise ValueError('ObjectID can only be added to relative ObjectID')
			other = other._value[1:]
		elif isinstance(other, str):
			other = tuple([int(x) for x in other.split('.')])
		elif not isinstance(other, tuple):
			return NotImplemented
		return ObjectID(self._value + other)
	def __eq__(self, other):
		return self._value == other._value if isinstance(other, ObjectID) else NotImplemented
	def __ne__(self, other):
		return self._value != other._value if isinstance(other, ObjectID) else NotImplemented
	def __hash__(self):
		return hash(self._value)
	def __len__(self):
		return len(self._value)
	def __getitem__(self, idx):
		return self._value[idx]
	def __str__(self):
		return '.'.join([str(n) if n is not None else '' for n in self._value])
	def __repr__(self):
		return 'OID({!r})'.format(str(self))
OID = ObjectID

class Sequence(list):
	__slots__ = []
	def get_pos(self, pos, count=1, default=None):
		assert count >= 1
		items = self[pos:pos+count]
		assert not any([isinstance(item, TaggedValue) for item in items])
		if len(items) < count:
			items += [default] * (count - len(items))
		return items if count != 1 else items[0]
	def find_tag(self, tag):
		if not isinstance(tag, tuple):
			tag = (CONTEXT, tag)
		return next((idx for idx, item in enumerate(self)
					if getattr(item, 'tag', None) == tag), -1)
	def get_tag(self, tag, type=None, default=None, encoding='BER', strict=True):
		if not isinstance(tag, tuple):
			tag = (CONTEXT, tag)
		return next((item.cast(type, encoding, strict) for item in self
					if getattr(item, 'tag', None) == tag), default)

class Set(list):
	__slots__ = []
	def get_tag(self, tag, type=None, default=None, encoding='BER', strict=True):
		if not isinstance(tag, tuple):
			tag = (CONTEXT, tag)
		return next((item.cast(type, encoding, strict) for item in self
					if getattr(item, 'tag', None) == tag), default)

class TaggedValue(object):
	__slots__ = ['tag', '_value']
	def __init__(self, tag, value, explicit=False):
		self.tag = tag if isinstance(tag, tuple) else (CONTEXT, tag)
		self._value = [value] if explicit else value
	def __repr__(self):
		return '{}: {!r}'.format(self.tag, self._value)
	def unpack(self):
		tagcls, tagnum = self.tag
		return tagcls, tagnum, self._value
	def cast(self, type, encoding='BER', strict=True):
		if type is None:  # explicit tagged item
			if not isinstance(self._value, list) or len(self._value) != 1:
				raise TypeError('not an explicit tagged type')
			return self._value[0]
		elif isinstance(self._value, list):
			return _decode_constructed(context, type, self._value)
		else:
			return _decode_primitive(context, type, self._value)

class EmbeddedValue(object):
	__slots__ = ['tag', 'ident', 'descriptor', 'value']
	def __init__(self, type, value, abstract=None, transfer=None, descriptor=None):
		if type not in (EXTERNAL, EMBEDDED_PDV, CHARACTER_STRING):
			raise ValueError('type must be one of EXTERNAL, EMBEDDED_PDV, CHARACTER_STRING')
		if abstract is not None and not isinstance(abstract, (ObjectID, int, long)):
			raise TypeError('abstract syntax must be an OID, int, or None')
		if transfer is not None and not isinstance(transfer, ObjectID):
			raise TypeError('transfer syntax must be an OID or None')
		if descriptor is not None and not isinstance(descriptor, basestring):
			raise TypeError('data value descriptor must be a string or None')
		if type == EXTERNAL and abstract is None:
			raise ValueError('invalid identification form for EXTERNAL type')
		self.tag = type
		self.ident = (abstract, transfer)
		self.descriptor = descriptor and ObjectDescriptor(descriptor)
		self.value = value
	def __repr__(self):
		return 'EmbeddedValue({}, {}, {!r}, {!r})'.format(self.tag, self.ident, self.descriptor, self.value)

# ===========================================================================

# ASN.1 Character String Definitions

def _charmap_codec(name, decoding_table, encoding_table):
	def encode(input, errors='strict'):
		return codecs.charmap_encode(input, errors, encoding_table)
	def decode(input, errors='strict'):
		return codecs.charmap_decode(input, errors, decoding_table)
	_codec_map[name] = codecs.CodecInfo(name=name, encode=encode, decode=decode)

def _restricted_codec(name, chars):
	INVALID = u'\uFFFE'
	decoding_table = (u''.join([INVALID for i in xrange(0x00, 0x20)]) +
					  u''.join([unichr(i) if (chars is None or chr(i) in chars) else INVALID
								for i in xrange(0x20, 0x7F)]) +
					  u''.join([INVALID for i in xrange(0x7F, 0x100)]))
	encoding_table = codecs.charmap_build(decoding_table)
	_charmap_codec(name, decoding_table, encoding_table)

def _teletex_codec(name):
	# this is actually ISO register entries 6 and 156, a (mostly) superset
	# of entries 102 and 103, as allowed by ITU-T rec X.680 
	decoding_table = (u''.join([unichr(i) for i in xrange(0xA0)]) +
					  u'\u00A0\u00A1\u00A2\u00A3\uFFFE\u00A5\uFFFE\u00A7'
					  u'\u00A4\u2018\u201C\u00AB\u2190\u2191\u2192\u2193'
					  u'\u00B0\u00B1\u00B2\u00B3\u00D7\u00B5\u00B6\u00B7'
					  u'\u00F7\u2019\u201D\u00BB\u00BC\u00BD\u00BE\u00BF'
					  u'\uFFFE\u0300\u0301\u0302\u0303\u0304\u0306\u0307'
					  u'\u0308\uFFFE\u030A\u0327\u0332\u030B\u0328\u030C'
					  u'\u2015\u00B9\u00AE\u00A9\u2122\u266a\u00AC\u00A6'
					  u'\uFFFE\uFFFE\uFFFE\uFFFE\u215B\u215C\u215D\u215E'
					  u'\u2126\u00C6\u00D0\u00AA\u0126\uFFFE\u0132\u013F'
					  u'\u0141\u00D8\u0152\u00BA\u00DE\u0166\u014A\u0149'
					  u'\u0138\u00E6\u0111\u00F0\u0127\u0131\u0133\u0140'
					  u'\u0142\u00F8\u0153\u00DF\u00FE\u0167\u014B\u00AD')
	encoding_table = codecs.charmap_build(decoding_table)
	_charmap_codec(name, decoding_table, encoding_table)

def _deferred_codec(name, other):
	_deferred_codec.other = None
	def encode(input, errors='strict'):
		if _deferred_codec.other or max(input) > u'\x7F':
			_deferred_codec.other = _deferred_codec.other or codecs.lookup(other)
			return _deferred_codec.other.encode(input, errors)
		else:
			return codecs.ascii_encode(input, errors)
	def decode(input, errors='strict'):
		if _deferred_codec.other or b'\x1B' in input:
			_deferred_codec.other = _deferred_codec.other or codecs.lookup(other)
			return _deferred_codec.other.decode(input, errors)
		else:
			return codecs.ascii_decode(input, errors)
	_codec_map[name] =  codecs.CodecInfo(name=name, encode=encode, decode=decode)

def _string_type(name, tag, encoding):
	cls = type(name, (CharacterString,), {'__slots__': [],
										  'tag': tag,
										  'encoding': encoding})
	_string_map[tag] = cls
	globals()[name] = cls

_codec_map = {}
_restricted_codec('numeric-string', "0123456789 ")
_restricted_codec('printable-string', "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
									  "abcdefghijklmnopqrstuvwxyz"
									  "0123456789 '()+,-./:=?")
_restricted_codec('visible-string', None)
_teletex_codec('teletex')
codecs.register(_codec_map.get)

_string_map = {}
_string_type('NumericString',   NUMERIC_STRING,   'numeric-string')
_string_type('PrintableString', PRINTABLE_STRING, 'printable-string')
_string_type('VisibleString',   VISIBLE_STRING,   'visible-string')
_string_type('IA5String',       IA5_STRING,       'ascii')
_string_type('TeletexString',   TELETEX_STRING,   'teletex')
_string_type('VideotexString',  VIDEOTEX_STRING,  'teletex')
_string_type('GraphicString',   GRAPHIC_STRING,   'latin-1')
_string_type('GeneralString',   GENERAL_STRING,   'latin-1')
_string_type('UTF8String',      UTF8_STRING,      'utf-8')
_string_type('BMPString',       BMP_STRING,       'utf-16-be')
_string_type('UniversalString', UNIVERSAL_STRING, 'utf-32-be')
_string_type('ObjectDescriptor',OBJECT_DESCRIPTOR,'latin-1')
_string_type('TimeType',        TIME,             'utf-8')

# ===========================================================================

# ASN.1 Date and Time Definitions

_datetime_map = {UTC_TIME:         ('%y%m%d%H%M%S', 12, True),
				 GENERALIZED_TIME: ('%Y%m%d%H%M%S', 14, True),
				 DATE:             ('%Y%m%d', None, False),
				 TIME_OF_DAY:      ('%H%M%S', None, False),
				 DATE_TIME:        ('%Y%m%d%H%M%S', None, False)}

_duration_re = re.compile(r'(?:(\d+)W)?(?:(\d+)D)?(?:T(?:(\d+)H)?(?:(\d+)M)?(?:(\d+)S)?)?')

class TimeZone(tzinfo):
	__slots__ = ['_name', '_offset']
	ZERO = timedelta(0)
	def __init__(self, tzname, tzoffset):
		self._name = tzname
		self._offset = timedelta(minutes=tzoffset)
	def utcoffset(self, dt):
		return self._offset
	def dst(self, dt):
		return TimeZone.ZERO
	def tzname(self, dt):
		return self._name
	@staticmethod
	def split(value):
		if value[-1:] == 'Z':
			return value[:-1], TimeZone.Zulu
		elif value[-5:-4] in ('-', '+'):
			tzm = int(value[-5]+'1')*(int(value[-4:-2])*60 + int(value[-2:]))
			return value[:-5], TimeZone(value[-5:], tzm)
		else:
			return value, None

TimeZone.UTC = TimeZone('UTC', 0)
TimeZone.Zulu = TimeZone('Z', 0)
TimeZone.Local = TimeZone(tzname[daylight], -(timezone, altzone)[daylight]//60)

# ===========================================================================

# ASN.1 helper functions

if PY3K:

	def btoui(value):
		return int.from_bytes(value, 'big', signed=False)

	def btosi(value):
		return int.from_bytes(value, 'big', signed=True)

	def uitob(value):
		length = (value.bit_length() + 7) // 8
		return value.to_bytes(length, 'big', signed=False)

	def sitob(value):
		length = (value + (value < 0)).bit_length() // 8 + 1
		return value.to_bytes(length, 'big', signed=True)

	def chr(i):
		return pack('b', i)

else:

	def btoui(value):
		return int(hexlify(value), 16)

	def btosi(value):
		i = int(hexlify(value), 16)
		if ord(value[0]) & 0x80:
			i -= 1 << (len(value) * 8)
		return i

	def uitob(value):
		assert value >= 0
		if isinstance(value, long):
			hexval = hex(value)[2:-1]
		else:
			hexval = hex(value)[2:]
		if len(hexval) & 1:
			hexval = '0' + hexval
		return unhexlify(hexval)

	def sitob(value):
		if value < 0:
			value += 0x100 << ((value + 1).bit_length() & ~7)
			value = uitob(value)
		else:
			value = uitob(value)
			if ord(value[0]) & 0x80:
				value = b'\0' + value
		return value

def _dump_element(write, elem):
	ident, length, content = elem
	write(ident)
	write(length)
	if isinstance(content, bytes):
		write(content)
	else:
		for elem in content:
			_dump_element(write, elem)

def _decoding_error(context, message):
	if context.strict:
		raise DecodingError('error decoding data at offset {}: {}'.format(context.offset, message))
	elif USE_LOGGING:
		log.warn('error decoding data at offset {}: {}'.format(context.offset, message))

def _encode_item(context, item):
	if isinstance(item, TaggedValue):
		tagcls, _tagnum, item = item.unpack()
		tagged = True
	else:
		tagcls = UNIVERSAL
		tagged = False
	ident = (tagcls << 6) & 0xC0
	if ((hasattr(item, '__iter__') and not isinstance(item, (bytes, StrType)))
			or isinstance(item, EmbeddedValue)):
		tagnum, value = _encode_constructed(context, item)
		constr = True
	else:
		tagnum, value = _encode_primitive(context, item)
		constr = False
	if tagged:
		tagnum = _tagnum
	if segsize and len(value) > segsize and (tagnum in _string_map
								or tagnum in (BIT_STRING, OCTET_STRING)):
		assert isinstance(value, bytes)
		r = range(0, len(value), segsize)
		value = [value[i:j] for i, j in zip(r, r[1:] + [None])]
		constr = True
	if not constr:
		assert isinstance(value, bytes)
		content = value
		itemlen = len(value)
	else:
		assert hasattr(item, '__iter__')
		ident |= 0x20
		content = []
		itemlen = 0
		for child in value:
			childlen, childval = _encode_item(context, child)
			if itemlen is not None and childlen is not None:
				itemlen += childlen
			else:
				itemlen = None
			content.append(childval)
		if encoding in ('DER', 'CER') and tagnum == SET:
			# Set component items must be ordered by their tags if this
			# is a SET, or else by their values if this is a SET OF.
			# We don't have enough information to completely determine
			# this ordering, but let's make a best-guess effort.
			if all(ord(elem[0]) & 0xC0 for elem in content):
				content.sort(key=lambda elem: elem[0])
			else:
				content.sort(key=lambda elem: elem[2])
		if encoding == 'CER':
			itemlen = None  # indefinite length form
	if tagnum < 0x1F:
		ident = chr(ident | tagnum)
	else:
		tagnum, byte = divmod(tagnum, 128)
		part = chr(byte)
		while tagnum:
			tagnum, byte = divmod(tagnum, 128)
			part = chr(byte | 0x80) + part
		ident = chr(ident | 0x1F) + part
	if itemlen is None:
		assert isinstance(content, list)
		content.append((b'\0', b'\0', b'')) # EOC sentinel for indefinite length form
		length = b'\x80'
	else:
		if itemlen < 0x80:
			length = chr(itemlen)
		else:
			length = uitob(itemlen)
			length = chr(0x80 | len(length)) + length
		itemlen += len(ident) + len(length)
	return itemlen, (ident, length, content)

def _encode_constructed(context, item):
	if isinstance(item, (Set, set, frozenset)):
		return SET, item
	elif isinstance(item, (Sequence, list, tuple)):
		return SEQUENCE, item
	elif isinstance(item, dict):
		return SET, item.items()
	elif isinstance(item, EmbeddedValue):
		abstract, transfer = item.ident
		if item.tag == EXTERNAL:
			if transfer is None:
				value = [abstract]
			else:
				value = [transfer, abstract]
			if item.descriptor:
				value.append(item.descriptor)
			if isinstance(item.value, BitString):
				value.append(TaggedValue(2, item.value))
			elif isinstance(item.value, bytes):
				value.append(TaggedValue(1, item.value))
			else:
				value.append(TaggedValue(0, item.value, True))
		else:
			if isinstance(abstract, ObjectID):
				if transfer is not None:
					ident = TaggedValue(0, [abstract, transfer])
				else:
					ident = TaggedValue(1, abstract)
			elif isinstance(abstract, (int, long)):
				if transfer is None:
					ident = TaggedValue(2, abstract)
				else:
					ident = TaggedValue(3, [abstract, transfer])
			else:
				if transfer is not None:
					ident = TaggedValue(4, transfer)
				else:
					ident = TaggedValue(5, None)
			value = [ident, item.value]
		return item.tag, value
	else:
		raise EncodingError('invalid ASN.1 constructed type: {}'.format(type(item)))

def _encode_primitive(context, item):
	if item is None:
		return NULL, b''
	elif isinstance(item, bool):
		return BOOLEAN, (b'\xFF' if item else b'\0')
	elif isinstance(item, Enumerated):
		return ENUMERATED, sltob(item)
	elif isinstance(item, (int, long)):
		return INTEGER, sltob(item)
	elif isinstance(item, float):
		s = math.copysign(1.0, item) == -1.0
		if item == 0.0:
			value = b'\x43' if s else b''
		elif math.isinf(item):
			value = b'\x41' if s else b'\x40'
		elif math.isnan(item):
			value = b'\x42'
		else:
			m, e = math.frexp(math.fabs(item))
			assert 0.5 <= m < 1
			i = 1
			while True:
				n = math.ldexp(m, i)
				if n.is_integer():
					break
				i += 1
			e -= i
			assert -1024 <= e <= 1024
			assert int(n) & 1 == 1
			e = sltob(e)
			n = ultob(int(n))
			byte = chr(0x80 | (0x40 if s else 0) | (len(e) - 1))  # binary, base = 2, scaling factor = 0
			value = byte + e + n
		return REAL, value
	elif USE_DECIMAL and isinstance(item, Decimal):
		if item.is_zero():
			value = b'\x43' if item.is_signed() else b''
		elif item.is_infinite():
			value = b'\x41' if item.is_signed() else b'\x40'
		elif item.is_nan():
			value = b'\x42'
		else:
			if context.encoding in ('CER', 'DER'):
				s, d, e = item.normalize().as_tuple()
				value = '{}{}.E{}'.format('-' if s else '',
										  ''.join(str(i) for i in d),
										  e or '+0')
			else:
				value = str(item)
			if PY3K:
				value = bytes(value, 'ascii')
			value = b'\x03' + value # decimal, NR3
		return REAL, value
	elif isinstance(item, BitString):
		if context.encoding in ('CER', 'DER') and item._pad:
			assert len(item) > 0
			mask = (1 << item._pad) - 1
			value = chr(item._pad) + item[:-1] + chr(ord(item[-1]) & ~mask)
		else:
			value =	 chr(item._pad) + item
		return BIT_STRING, value
	elif isinstance(item, bytes):
		return OCTET_STRING, item
	elif isinstance(item, ObjectID):
		assert len(item) >= 2
		if item[0] is None:
			tag = RELATIVE_OID
			item = item[1:]
		else:
			tag = OBJECT_IDENTIFIER
			item = (item[0]*40 + item[1],) + item[2:]
		value = []
		for valn in item:
			valn, byte = divmod(valn, 128)
			part = chr(byte)
			while valn:
				valn, byte = divmod(valn, 128)
				part = chr(byte | 0x80) + part
			value.append(part)
		return tag, b''.join(value)
	elif isinstance(item, IRIString):
		tag = OID_IRI if item.startswith('/') else RELATIVE_OID_IRI
		return tag, item.encode('utf-8')
	elif isinstance(item, CharacterString):
		return item.tag, item.encode(item.encoding)
	elif isinstance(item, unicode):
		strtype = context.strtype or IA5String
		return strtype.tag, item.encode(strtype.encoding)
##		if strtype is not None:
##			return strtype.tag, item.encode(strtype.encoding)
#		elif max(item) < '\x80':
##		else:
##			return IA5String.tag, item.encode(IA5String.encoding)
#		else:
#			return GENERAL_STRING, item.encode(GeneralString.encoding)
	elif isinstance(item, (date, time)):
		if isinstance(item, datetime):
			if item.tzinfo is TimeZone.UTC:
				tag = UTC_TIME
			elif item.tzinfo:
				tag = GENERALIZED_TIME
			else:
				tag = DATE_TIME
		elif isinstance(item, date):
			tag = DATE
		elif isinstance(item, time):
			tag = TIME_OF_DAY
		format, fmtlen, aware = _datetime_map[tag]
		if tag == GENERALIZED_TIME and item.microsecond:
			format += '{}'
			frac = str(item.microsecond / 1000000.0)[1:]
		else:
			frac = None
		if aware:
			assert item.tzinfo is not None
			if context.encoding in ('CER', 'DER'):
				item = item.astimezone(TimeZone.Zulu)
			if item.utcoffset():
				format += '%z'
			else:
				format += 'Z'
		value = item.strftime(format).format(frac)
		if PY3K:
			value = bytes(value, 'ascii')
		return tag, value
	elif isinstance(item, timedelta):
		d = item.days
		h, s = divmod(item.seconds, 3600)
		m, s = divmod(s, 60)
		return DURATION, b'{}DT{}H{}M{}S'.format(d, h, m, s)
	else:
		raise EncodingError('invalid ASN.1 primitive type: {}'.format(type(item)))

def _decode_item(context, file):

	def read(length):
		value = file.read(length)
		if len(value) != length:
			_decoding_error(context, 'insufficient data')
			if not value:
				raise EOFError
		context.offset += len(value)
		return value

	ident = ord(read(1))
	tagnum = ident & 0x1F
	tagcls = ident >> 6
	constr = bool(ident & 0x20)
	if tagnum == 0x1F:
		tagnum = 0
		while True:
			byte = ord(read(1))
			tagnum = (tagnum << 7) | (byte & 0x7F)
			if tagnum == 0:
				_decoding_error(context, 'invalid identifier form')
			if byte & 0x80 == 0:
				break
		if tagnum < 31:
			_decoding_error(context, 'invalid identifier form')
	length = ord(read(1))
	if length == 0x80:  # indefinite form
		length = None
	elif length & 0x80:  # definite long form
		if length == 0xFF:
			_decoding_error(conetxt, 'invalid long form length')
		length = btoui(read(length & 0x7F))
		if length <= 0x7F and context._encoding in ('CER', 'DER'):
			_decoding_error(context, 'invalid long form length')
	if not constr:
		if length is None:
			_decoding_error(context, 'invalid primitive type length')
			value = b''  # XXX not sure it makes sense to try to keep going at this point
		else:
			value = read(length)
	else:
		if context._encoding == 'CER' and length is not None:
			_decoding_error(context, 'invalid definite length form')
		elif context._encoding == 'DER' and length is None:
			_decoding_error(context, 'invalid indefinite length form')
		value = []
		if length is not None:
			end_offset = context._offset + length
		try:
			while length is None or context._offset < end_offset:
				item = _decode_item(context, file)
				if item is StopIteration:
					if length is not None:
						_decoding_error(context, 'invalid definite length form')
					break
				value.append(item)
			else:
				assert length is not None
				if context._offset != end_offset:
					_decoding_error(context, 'invalid constructed type length')
		except EOFError:
			pass
	if tagcls != UNIVERSAL or context._schema:
		item = TaggedValue((tagcls, tagnum), value)
	elif constr:
		item = _decode_constructed(context, tagnum, value)
	else:
		item = _decode_primitive(context, tagnum, value)
	return item

def _decode_constructed(context, tag, value):
	assert isinstance(value, list)
	if tag == SEQUENCE:
		return Sequence(value)
	elif tag == SET:
		# it is tempting to EAFP rather than LBYL here, but tests with timeit
		# show that this way is actually faster in the most common cases
		if all([isinstance(item, Sequence) and len(item) == 2 and 
				item[0].__hash__ for item in value]):
			return dict(value)
		elif all([item.__hash__ for item in value]):
		   return set(value)
		else:
			return Set(value)
	elif tag == EXTERNAL:
		idx = 0
		abstract = transfer = descriptor = None
		if isinstance(value[idx], ObjectID):
			abstract = value[idx]
			idx += 1
		if isinstance(value[idx], (int, long)):
			transfer = abstract
			abstract = value[idx]
			idx += 1
		if isinstance(value[idx], ObjectDescriptor):
			descriptor = value[idx]
			idx += 1
		tagcls, tagnum = value[idx].tag
		if tagnum == 0:
			value = value[idx].cast(None)
		elif tagnum == 1:
			value = value[idx].cast(OCTET_STRING, encoding, strict)
		elif tagnum == 2:
			value = value[idx].cast(BIT_STRING, encoding, strict)
		return EmbeddedValue(EXTERNAL, value, abstract, transfer, descriptor)
	elif tag in (EMBEDDED_PDV, CHARACTER_STRING):
		ident, value = value
		tagcls, tagnum = ident.tag
		if tagnum in (0, 3):
			abstract, transfer = ident.cast(SEQUENCE, encoding, strict)
		elif tagnum == 1:
			abstract, transfer = ident.cast(OBJECT_IDENTIFIER, encoding, strict), None
		elif tagnum == 2:
			abstract, transfer = ident.cast(INTEGER, encoding, strict), None
		elif tagnum == 4:
			abstract, transfer = None, ident.cast(OBJECT_IDENTIFIER, encoding, strict)
		else:
			abstract = transfer = None
		return EmbeddedValue(tag, value, abstract, transfer)
	elif tag == BIT_STRING:
		if context._encoding == 'DER':
			_decoding_error(context, 'invalid constructed BIT_STRING')
		# unlike the case above, EAFP is faster here for the most common case
#		if all([isinstance(item, BitString) for item in value]):
		try:
			return BitString(value[-1]._pad if value else 0, b''.join(value))
		except:
			pass
	elif tag == OCTET_STRING:
		if context._encoding == 'DER':
			_decoding_error(context, 'invalid constructed OCTET_STRING')
#		if all([isinstance(item, bytes) for item in value]):
		try:
			return b''.join(value)
		except:
			pass
	elif tag in _string_map:
		cls = _string_map[tag]
		if context._encoding == 'DER':
			_decoding_error(context, 'invalid constructed {}'.format(cls.__name__))
#		if all([isinstance(item, bytes) for item in value]):
		try:
			return cls(b''.join(value), cls.encoding)
		except:
			pass
	_decoding_error(context, 'invalid constructed type {}: {}'.format(tag, value))
	return TaggedValue((UNIVERSAL, tag), value)

def _decode_primitive(context, tag, value):
	assert isinstance(value, bytes)
	if tag == EOC:
		if value:
			_decoding_error(context, 'invalid EOC: {!r}'.format(value))
		return StopIteration
	elif tag == NULL:
		if not value:
			return None
	elif tag == BOOLEAN:
		if len(value) == 1:
			return value != b'\0'
	elif tag == ENUMERATED:
		if value:
			return Enumerated(btosi(value))
	elif tag == INTEGER:
		if value:
			return btosi(value)
	elif tag == REAL:
		if not value:
			return 0.0
		byte = ord(value[0])
		kind = byte >> 6
		if kind == 0:  # decimal encoding
			return float(value[1:])
		elif kind == 1:  # special value
			if len(value) != 1:
				pass
			elif byte == 0x40:
				return float('+inf')
			elif byte == 0x41:
				return float('-inf')
			elif byte == 0x42:
				return float('nan')
			elif byte == 0x43:
				return -0.0
		else:
			s = -1 if (byte & 0x40) else +1
			b = (byte >> 4) & 0x03
			f = (byte >> 2) & 0x03
			i = (byte & 0x03) + 2
			e = btosl(value[1:i])
			n = btoul(value[i:])
			m = s * math.ldexp(n, f)
			if b == 0:  # base 2
				return math.ldexp(m, e)
			elif b == 1:  # base 8
				return m * math.pow(8, e)
			elif b == 2:  # base 16
				return m * math.pow(16, e)
	elif tag == BIT_STRING:
		if context._encoding == 'CER' and len(value) > 1000:
			_decoding_error(context, 'invalid primitive BIT_STRING')
		if value:
			try:
				return BitString(ord(value[0]), value[1:])
			except ValueError:
				pass
	elif tag == OCTET_STRING:
		if context._encoding == 'CER' and len(value) > 1000:
			_decoding_error(context, 'invalid primitive OCTET_STRING')
		return value
	elif tag in (OBJECT_IDENTIFIER, RELATIVE_OID):
		oid = []
		valn = 0
		for byte in value:
			byte = ord(byte)
			valn = (valn << 7) | (byte & 0x7F)
			if byte & 0x80 == 0:
				oid.append(valn)
				valn = 0
		if oid and valn == 0:
			if tag == OBJECT_IDENTIFIER:
				x = min(oid[0]//40, 2)
				y = oid[0] - x*40
				return ObjectID([x, y], oid[1:])
			else:
				return ObjectID([None], oid)
	elif tag in (OID_IRI, RELATIVE_OID_IRI):
		try:
			return IRIString(value, 'utf-8')
		except UnicodeError:
			pass
	elif tag in _string_map:
		cls = _string_map[tag]
		if context._encoding == 'CER' and len(value) > 1000:
			_decoding_error(context, 'invalid primitive {}'.format(cls.__name__))
		try:
			return cls(value, cls.encoding)
		except UnicodeError:
			pass
	elif tag in _datetime_map:
		format, fmtlen, aware = _datetime_map[tag]
		if aware:
			value, tzone = TimeZone.split(value)
			if (tag == UTC_TIME and tzone is None) or (context._encoding in ('CER', 'DER') and tzone is not TimeZone.Zulu):
				_decoding_error(context, 'invalid time zone: {!r}'.format(value))
			if tzone is None:
				tzone = TimeZone.UTC if tag == UTC_TIME else TimeZone.Local
		if fmtlen and fmtlen > len(value):
			if context._encoding in ('CER', 'DER'):
				_decoding_error(context, 'invalid time value: {!r}'.format(value))
			format = format[:len(value)-fmtlen]
		if tag == GENERALIZED_TIME:
			value, _, frac = value.partition('.')
		try:
			value = datetime.strptime(value, format)
		except ValueError:
			pass
		else:
			if aware:
				value = value.replace(tzinfo=tzone)
			if tag == UTC_TIME:
				value = value.astimezone(TimeZone.UTC)
			elif tag == DATE:
				value = value.date()
			elif tag == TIME_OF_DAY:
				value = value.time()
			elif tag == GENERALIZED_TIME and frac:
				frac = float('.'  + frac)
				if len(format) == 12:
					value += timedelta(seconds=frac)
				elif len(format) == 10:
					value += timedelta(minutes=frac)
				elif len(format) == 8:
					value += timedelta(hours=frac)
				elif len(format) == 6:
					value += timedelta(days=frac)
			return value
	elif tag == DURATION:
		match = _duration_re.match(value)
		if match.lastindex:
			w, d, h, m, s = match.groups(0)
			return timedelta(weeks=w, days=d, hours=h, minutes=m, seconds=s)
	_decoding_error(context, 'invalid primitive type {}: {}'.format(tag, value))
	return TaggedValue((UNIVERSAL, tag), value)

class SchemaType(type):
	def __new__(mcls, name, bases, dict):
		pass
		
class SchemaBase:
	__metaclass__ = SchemaType

#def _decode_tagval(context, typedef, value):
#	tag, type, flags, members = typedef
#	if not isinstance(type, int):
#		return _decode_schema(context, typedef, value)
#	tagcls, tagnum = tag
#	assert tagcls == UNIVERSAL
#	if EXPLICIT in flags:
#		if not isinstance(value, list) or len(value) != 1:
#			_decoding_error(context, 'not an explicit tagged type')
#		return value[0]
#	elif isinstance(value, list):
#		return _decode_constructed(context, tagnum, value)
#	elif isinstance(value, bytes):
#		return _decode_primitive(context, tagnum, value)
#	else:
#		raise TypeError('invalid tagged value type {}'.format(type(value)))

def _decode_schema(context, typedef, value):
	def _decode_tagval(tag, explicit, type, value):
		if not isinstance(type, int):
			if not isinstance(type, tuple):
				assert hasattr(type, '_typedef')
				type = type._typedef
			return _decode_schema(context, type, value)
		tagcls, tagnum = tag
		assert tagcls == UNIVERSAL
		if explicit:
			if not isinstance(value, list) or len(value) != 1:
				_decoding_error(context, 'not an explicit tagged type')
			return value[0]
		elif isinstance(value, list):
			return _decode_constructed(context, tagnum, value)
		elif isinstance(value, bytes):
			return _decode_primitive(context, tagnum, value)
		else:
			raise TypeError('invalid tagged value type {}'.format(type(value)))
#	if not isinstance(schema, SchemaBase):
#		raise TypeError('not a valid schema type')
	if not isinstance(value, TaggedValue):
		raise TypeError('not a valid tagged type')
#	tag, type, flags, members = schema._typedef
	tag, explicit, type, members = typedef
	if tag != value.tag:
		_decoding_error(context, 'schema tag mismatch')
	if not members:
		return decode_tagval(tag, explicit, type, value)
	schemaobj = schema()
	idx = 0
	for name, typedef, flag, default in members:
		tag, explicit, type, members = typedef
		if value[idx].tag == tag:
			item = _decode_tagval(tag, explicit, type, value[idx])
			setattr(schemaobj, name, item)
			idx += 1
		elif type == CHOICE:
			pass
		elif DEFAULT in flags:
			setattr(schemaobj, name, default)
		elif OPTIONAL not in flags:
			_decoding_error(context, 'missing required schema member {}'.format(name))

class Type1(object):
	_typedef = ((UNIVERSAL, 26), IMPLICIT, VisibleString, None)

class Type2(object):
	_typedef = ((APPLICATION, 3), IMPLICIT, Type1, None)

class Type3(object):
	_typedef = ((CONTEXT, 2), EXPLICIT, Type2, None)

class Type4(object):
	_typedef = ((APPLICATION, 7), IMPLICIT, Type3, None)

class Type5(object):
	_typedef = ((CONTEXT, 2), IMPLICIT, Type2, None)

class ExternalType(object):
	_typedef = ((UNIVERSAL, 8), IMPLICIT, SEQUENCE, [
					('direct_reference',      ((UNIVERSAL, 6), IMPLICIT, OBJECT_IDENTIFIER, None), OPTIONAL, None),
					('indirect_reference',    ((UNIVERSAL, 2), IMPLICIT, INTEGER, None), OPTIONAL, None),
					('data_value_descriptor', ((UNIVERSAL, 7), IMPLICIT, ObjectDescriptor, None), OPTIONAL, None),
					('encoding',              (None, None, CHOICE, [
							('single_ASN1_type', ((CONTEXT, 0), EXPLICIT, ANY, None), None, None),
							('octet_aligned',    ((CONTEXT, 1), IMPLICIT, OCTET_STRING, None), None, None),
							('arbitrary',        ((CONTEXT, 2), IMPLICIT, BIT_STRING, None), None, None)
						]), None, None)
					])

class EmbeddedType(object): # (SchemaBase):
	foo = ([UNIVERSAL,8],IMPLICIT, SEQUENCE, [
				('direct_reference', OBJECT_IDENTIFIER, OPTIONAL),
				('indirect_reference', INTEGER, OPTIONAL),
				('data_value_descriptor', OBJECT_DESCRIPTOR, OPTIONAL),
				('encoding', CHOICE, [
					('single_asn1_type', [0], ANY),
					('octet_aligned', [1], IMPLICIT, OCTET_STRING),
					('arbitrary', [2], IMPLICIT, BIT_STRING)])])